#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
// #define ONLINE_JUDGE
const int N = 35;

int f[N][N]; // 从i个数里选j个数的方案数，即组合数
int l, r, K, B; // K是能用的1的个数，B是B进制

void init()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
            if(!j) f[i][j] = 1; // 从i个数里选0个数的方案数为1
            else f[i][j] = f[i-1][j] + f[i-1][j-1];

}

// 求区间[0,n]中的 “满足条件的数” 的个数
// “满足条件的数”是指：一个数的B进制表示，其中有K位是1、其他位全是0
int dp(int n)
{
    if(!n) return 0; // 如果上界是0，则就是0种

    vector<int> nums; // n在B进制下的每一位
    while(n) nums.push_back(n % B), n /= B;

    int res = 0; // 最终返回答案，[0, n]中有多少合法数

    int last = 0; // 前面有多少个1，则当前还能用K - last个1

    for(int i = nums.size() - 1; i >= 0; i--)
    {
        int x = nums[i];

        if(x) // 求其他分支的数的个数， x>0才存在分支情况
        {
            // 枚举当前位为0, 从剩下的所有位（共有i位）中选K-last个数
            res += f[i][K - last];

            if(x > 1)
            {
                // 当前位填1，从剩下的所有位（共有i位）中选K-last-1个数
                // 对应左分支填1的情况
                if(K - last - 1 >= 0) res += f[i][K -last -1];// i个数中选K-last-1个数填1的组合数是多少
                // 对应左分支填>1, 此时右分支的情况
                break;
            }
            else  // x == 1 右取1，左取0
            {
                last++;
                // 如果已经填的数last超过限制K, 则直接break
                if(last > K) break;
            }
        }
        // 上面枚举完所有的左分支，下面处理右分支
        // 遍历到最后一位，即i == 0, 并且最后一位取0，此时是一个合法结果,如果最后一位不为0, 则在上面被处理过了
        if(i == 0 && last == K) res++; 
    }
    return res; 
}

signed main() 
{

    #ifdef ONLINE_JUDGE

    #else
    freopen("./in.txt","r",stdin);
    #endif
    ios::sync_with_stdio(false);
	cin.tie(0);

    init();
    cin >> l >> r >> K >> B;
    cout << dp(r) - dp(l-1) << endl;
    return 0;
}

